package exam.test4;


import java.util.Arrays;

class RecursionAvg {

    public static void main(String[] args) {
        IntLinkedList list = new IntLinkedList();
        list.addAll(new int[]{5, 8, 2, 9, 4, 2});  // avg = 5.0

        System.out.println("common.list: " + list);
        System.out.println("avg: " + avg(list));
    }

    public static int sum(IntLinkedList list, int startIndex, int sum) {
        if (startIndex >= list.getSize()) {
            return sum;
        }
        sum += list.get(startIndex++);
        return sum(list, startIndex, sum);
    }

    public static double avg(IntLinkedList list) {
        if (list.getSize() == 0) {
            return 0D;
        }
        return (double) sum(list, 0, 0) / list.getSize();
    }



    public boolean binSearchOne(int[] a, int value) {
        if (a.length == 0) {
            return false;
        } else {
            int mid = (a.length - 1) / 2;
            if (a[mid] == value) {
                return true;
            } else if (value < a[mid]) {
                int[] sub = Arrays.copyOfRange(a, 0, mid);
                return binSearchOne(sub, value);
            } else {
                int[] sub = Arrays.copyOfRange(a, mid + 1, a.length);
                return binSearchOne(sub, value);
            }
        }
    }


    public boolean binSearch(int [] a, int value) {
        return binSearchHelper(a, value, 0, a.length - 1);
    }

    public boolean binSearchHelper(int [] a, int value, int start, int end){
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;
        if (a[mid] == value) {
            return true;
        } else if (value < a[mid]) {
            return binSearchHelper(a, value, start, mid - 1);
        } else {
            return binSearchHelper(a, value, mid + 1, end);
        }
    }
}

class Node{
    public int value;
    public Node next;

    public Node(int newVal){
        value = newVal;
    }

    public String toString(){
        return String.valueOf(this.value);
    }
}

class IntLinkedList {

    private Node head;
    private Node tail;
    private int size;

    public IntLinkedList(){

    }

    public int getSize() {
        return size;
    }

    public void add(int j){
        Node n = new Node(j);
        if(this.head == null){
            this.head = n;
        } else {
            this.tail.next = n;
        }
        this.tail = n;
        this.size++;
    }

    public int get(int index) {
        if (index >= size) {
            return -1;
        }
        Node cur = this.head;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        return cur.value;
    }

    public void addAll(int[] arrays) {
        for (int i = 0; i < arrays.length; i++) {
            add(arrays[i]);
        }
    }

    public String toString(){
        String s = "[";
        Node cur = head;
        while(cur != null){
            s = s + cur.value + "->";
            cur = cur.next;
        }
        s += "]";
        return s;
    }

}




